package chapter04_RecursionAndDynamic;

import java.util.HashMap;
import java.util.Map;

/**
 * 描述：最小包含子串
 *      给定字符串str1和str2，求str1的子串包含所有str2字符的最小子串长度
 * @author hl
 * @date 2021/9/26 21:25
 */
public class MinLength {
    public static void main(String[] args) {
        String str1 = "adabbca";
        String str2 = "acb";
//        String str1 = "adcae";
//        String str2 = "ac";
        MinLength main = new MinLength();
        int res = main.minLength(str1, str2);
        System.out.println(res);
    }


    public int minLength(String str1, String str2){
        if (str1 == null || str2 == null || str1.length() < str2.length()) {
            return 0;
        }
        //left：str1子串的左边界，right：str1子串的右边界，minLen就是返回值
        int left = 0, right = 0, minLen = Integer.MAX_VALUE;
        //表示在str[left...right]子串中还欠str2多少个字符
        int match = str2.length();
        //表示遍历过程中目前str1还欠str2 key字符value个
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < str2.length(); i++) {
            map.put(str2.charAt(i), map.getOrDefault(str2.charAt(i), 0) + 1);
        }
        char ch;
        int curNum;
        while(right < str1.length()){
            ch = str1.charAt(right);
            map.put(ch, map.getOrDefault(ch, 0) - 1);
            match = map.get(ch) < 0 ? match : match - 1;
            //尽可能地缩小left...right的范围，直到不能再缩小，此时是以left开头满足条件的最小子串长度
            if (match == 0) {
                while(map.get(str1.charAt(left)) < 0){
                    map.put(str1.charAt(left++), map.get(str1.charAt(left)) + 1);
//                    left++;
                }
                map.put(str1.charAt(left), map.get(str1.charAt(left)) + 1);
                minLen = Math.min(minLen, right - left++ + 1);
                match++;
            }
            right++;
        }
        return minLen;
    }
}
